#ifndef BINARY_SEARCH_TREE_H
#include <iostream>
#include "dsexceptions.h"

using namespace std; 


//---------------------------------------------------------------------抽象模板类
template<typename DT>
class Node  //抽象类Node
{
private:
    DT element;
public:
    virtual DT getElement() const {return element;}
    virtual void setElement(DT _val) {element = _val;}
    Node(DT _val) {element = _val;}
};

template<typename DT>
class BinaryTree   //抽象类BinaryTree和其中由抽象类Node派生出的抽象类BinaryNode
{
private:
    //-------------------------------从Node<DT>派生出BinaryNode, 
	class BinaryNode : public Node<DT>
    {
    private:
        BinaryNode *left;
        BinaryNode *right;
    };
    BinaryNode *root;
    
    typedef struct {
        BinaryNode *root;
    }BiTree;

public:
    //简单定义纯虚函数
    virtual void insert( const DT & x ) = 0;

    virtual void insert( DT && x ) = 0;
    
    virtual void remove( const DT & x ) = 0;

    virtual void printTree( ostream & out = cout ) const = 0;
};



//----------------------------------------------------------------具体类：实际调用函数测试
template <typename DT>
class SimpleTree : public BinaryTree<DT>
{
public:
    //一些基本函数：constructor, =...
    SimpleTree( ) : root{ nullptr }{}

    SimpleTree( const SimpleTree & rhs ) : root{ nullptr }
    {
		root = clone( rhs.root );
    }

    SimpleTree( SimpleTree && rhs ) : root{ rhs.root }
    {
		rhs.root = nullptr;
    }
    
    SimpleTree & operator=( const SimpleTree & rhs )
    {
        SimpleTree copy = rhs;
        std::swap( *this, copy );
        return *this;
    }
    SimpleTree & operator=( SimpleTree && rhs )
    {
        std::swap( root, rhs.root );
        return *this;
    }


    void insert( const DT & x )  //实现父类BinaryTree中定义的纯虚函数
    {
        insert( x, root );   //接口，调用private中重载的函数，下insert、remove、printTree同
    }
     
    void insert( DT && x )  //实现父类BinaryTree中定义的纯虚函数
    {
        insert( std::move( x ), root );
    }
    
    void remove( const DT & x )   //实现父类BinaryTree中定义的纯虚函数1
    {
        remove( x, root );
    }

    const DT & findMin( ) const
    {
        if( isEmpty( ) )
            throw UnderflowException{ };
        return findMin( root )->element;
    }

    bool isEmpty( ) const
    {
        return root == nullptr;
    }

    void printTree( ostream & out = cout ) const   //实现父类BinaryTree中定义的纯虚函数1
    {
        if( isEmpty( ) )
            out << "Empty tree" << endl;
        else
            printTree( root, out );
    }

private:
    struct SimpleNode   //定义节点Node并初始化
    {
        DT element;
        SimpleNode *left;
        SimpleNode *right;

        SimpleNode( const  DT & theElement,SimpleNode *lt, SimpleNode *rt )
			: element{ theElement }, left{ lt }, right{ rt } { }
        
        SimpleNode(  DT && theElement, SimpleNode *lt, SimpleNode *rt )
          : element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
    };

    SimpleNode *root;
    
    typedef struct {
        SimpleNode *root;
    }BiTree;
    
    void insert( const DT & x, SimpleNode * & t )  //BinaryTree中纯虚函数 -> SimpleTree的public -> private，最后实现了虚函数
    {                                              //下insert、remove、printTree同
        if( t == nullptr )
            t = new SimpleNode{ x, nullptr, nullptr };
        else if( x < t->element )
            insert( x, t->left );
        else if( t->element < x )
            insert( x, t->right );
        else
            ; 
    }

    void insert( DT && x, SimpleNode * & t )
    {
        if( t == nullptr )
            t = new SimpleNode{ std::move( x ), nullptr, nullptr };
        else if( x < t->element )
            insert( std::move( x ), t->left );
        else if( t->element < x )
            insert( std::move( x ), t->right );
        else
            ; 
    }

    void remove( const DT & x, SimpleNode * & t )
    {
        if( t == nullptr )
            return;   
        if( x < t->element )
            remove( x, t->left );
        else if( t->element < x )
            remove( x, t->right );
        else if( t->left != nullptr && t->right != nullptr ) 
        {
            t->element = findMin( t->right )->element;
            remove( t->element, t->right );
        }
        else
        {
            SimpleNode *oldNode = t;
            t = ( t->left != nullptr ) ? t->left : t->right;
            delete oldNode;
        }
    }

    void makeEmpty( SimpleNode * & t )
    {
        if( t != nullptr )
        {
            makeEmpty( t->left );
            makeEmpty( t->right );
            delete t;
        }
        t = nullptr;
    }

    SimpleNode * findMin( SimpleNode *t ) const
    {
		/// 这个函数用了递归.
        if( t == nullptr )
            return nullptr;
        if( t->left == nullptr )
            return t;
        return findMin( t->left );
    }

    void printTree( SimpleNode *t, ostream & out ) const
    {
        if( t != nullptr )
        {
            printTree( t->left, out );
            out << t->element << endl;
            printTree( t->right, out );
        }
    }

    SimpleNode * clone( SimpleNode *t ) const
    {
        if( t == nullptr )
            return nullptr;
        else
            return new SimpleNode{ t->element, clone( t->left ), clone( t->right ) };
    }
};
#endif